Context Free Grammar (MCA sem-2, MSc.(IT) -4)

---

Context-Free Grammars

A context-free grammar basically consists of a finite set of grammar rules. In order to define grammar rules, we assume that we have two kinds of symbols: the terminals, which are the symbols of the alphabet underlying the languages under consideration, and the nonterminals, which behave like variables ranging over strings of terminals. A rule is of the form A → α, where A is a single nonterminal, and the right-hand side α is a string of terminal and/or nonterminal symbols.

 

A context-free grammar is a 4-tuple (V, T, P,S) where

1. V is a finite set called the variables
2. T is a finite set called the terminals
3. P is a finite set of rules, called productions.
4. S ∈ V is the start variable.

Example

            Grammar G: ({S, A, B}, {a, b}, S, {S →AB, A →a, B →b})

            Here,

S, A, and B are Non-terminal symbols;

a and b are Terminal symbols

S is the Start symbol

Productions, P : S →AB, A →a, B →b

 

---

---